package code;

import java.util.Arrays;

public class Arr {

    public static void main(String[] args) {
        int[] arr = {1,2,3};
        int[] res = searchRange(arr, 2);
        System.out.println(Arrays.toString(res));
    }

    public static int[] searchRange(int[] nums, int target) {
        // 二分查找法
        // 查找最左边
        int first = binarySearchLeftIndex(nums,target,true);
        int last = binarySearchLeftIndex(nums,target,false);
        // 查找最右边
        return new int[]{first,last};
    }


    /**
     * 二分查找：在有序数组中找某个数的最左/最右
     */
    public static int binarySearchLeftIndex(int[] arr,int target,boolean islLeft) {
        int l = 0; // 左边界
        int r = arr.length -1;// 右边界
        int right = -1,left = -1;
        while (l <= r) {
            int mid = (l+r) / 2;
            if(arr[mid] > target) {// 目标在左区间
                r = mid - 1;
            }
            else if (arr[mid] < target) {// 目标在右区间
                l = mid + 1;
            }
            if(arr[mid] == target) {// 找到最左边的下标
                if(islLeft) {
                    left = mid;
                    r = mid - 1;
                } else {
                    right = mid;
                    l = mid + 1;
                }
            }
        }
        return islLeft ? left : right;
    }



}
